/**
 * Definition for a binary tree node. */
export class TreeNode {
    val: number
    left: TreeNode | null
    right: TreeNode | null
    constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
        this.val = (val===undefined ? 0 : val)
        this.left = (left===undefined ? null : left)
        this.right = (right===undefined ? null : right)
    }
}

// 队列: FIFO：先进先出
export class Queue<T> {
    private items:T[]
    constructor(){
        this.items = []
    }
    add(...element:T[]):void {
        this.items.push(...element)
    }
    remove():T {
        return this.items.shift()
    }
    front():T {
        return this.items[0]
    }
    size():number {
        return this.items.length
    }
    isEmpty():boolean {
        return this.items.length === 0
    }
    clear():void {
        this.items = [];
    }
    print():void {
        console.log(this.items.toString())
    }
}



// https://leetcode.cn/problems/ping-heng-er-cha-shu-lcof/
// https://leetcode.cn/problems/add-two-numbers/
// 字符串转二叉树
export function stringToTreeNode(input: string): TreeNode | null {
    input = input.trim()
    input = input.substring(1, input.length-1);
    if (input.length == 0) {
        return null;
    }
    const parts: string[] = input.split(",");
    let item: string = parts[0];
    let root: TreeNode | null = new TreeNode(parseInt(item));
    const nodeQueue: Queue<TreeNode | null> = new Queue<TreeNode | null>();
    nodeQueue.add(root);
    let index: number = 1;
    while (!nodeQueue.isEmpty()) {
        let node: TreeNode | null = nodeQueue.remove();

        if (index == parts.length) {
            break;
        }

        item = parts[index++];
        item = item.trim();
        if (item != "null") {
            let leftNumber: number = parseInt(item);
            node.left = new TreeNode(leftNumber);
            nodeQueue.add(node.left);
        }
        // 提示重复，这个应该不是故意重复的？！
        if (index == parts.length) {
            break;
        }

        item = parts[index++];
        item = item.trim();
        if (item != "null") {
            let rightNumber: number = parseInt(item);
            node.right = new TreeNode(rightNumber);
            nodeQueue.add(node.right);
        }
    }
    return root;
}

export function treeNodeToString(root: TreeNode | null): string {
    if (root == null) {
        return "[]";
    }
    let output: string = "";
    const nodeQueue: Queue<TreeNode | null> = new Queue<TreeNode | null>();
    nodeQueue.add(root);
    while (!nodeQueue.isEmpty()) {
        let node: TreeNode | null = nodeQueue.remove();
        if (node == null) {
            output += "null, ";
            continue;
        }
        output += node.val + ", ";
        nodeQueue.add(node.left);
        nodeQueue.add(node.right);
    }
    return "[" + output.substring(0, output.length-2) + "]";
}

function prettyPrintTree(node: TreeNode | null, prefix: string, isLeft: boolean) {
    if (node == null) {
        console.log("Empty tree");
        return;
    }
    if (node.right != null) {
        prettyPrintTree(node.right, prefix + (isLeft ? "│   " : "    "), false);
    }
    console.log(prefix + (isLeft ? "└── " : "┌── ") + node.val);
    if (node.left != null) {
        prettyPrintTree(node.left, prefix + (isLeft ? "    " : "│   "), true);
    }
}

// 和java不一样，不能和上面同名 prettyPrintTree 报错！
export function prettyPrintTreeNode(node: TreeNode | null) {
    prettyPrintTree(node,  "", true);
}
